//188K 0MS 
#include<iostream>
#include<cstring>
using namespace std;

// 表示2*2矩阵类型
struct Matrix
{
	// 数据
	int data[2][2];
	
	// 构造函数
	Matrix() {}
	Matrix(int x00,int x01,int x10,int x11)
	{
		data[0][0]=x00;
		data[0][1]=x01;
		data[1][0]=x10;
		data[1][1]=x11;
	}
};

// 返回矩阵A和B相乘的结果
Matrix multiply(Matrix& A, Matrix& B)
{
	Matrix C;
	memset(C.data,0,sizeof(C.data));
	
	// 相乘
	for(int i=0; i<2; i++)
		for(int j=0; j<2; j++)
			for(int k=0; k<2; k++)
			{
				C.data[i][j]+=A.data[i][k]*B.data[k][j];
				C.data[i][j]%=10000;
			}
	return C;
}

// 求A^n的快速幂算法
Matrix quick_pow(Matrix& A, int n)
{
	// 置ans为单位矩阵
	Matrix ans(1, 0, 0, 1);
	
	// 快速幂
	while(n!=0)
	{
		if (n & 1)
			ans = multiply(ans,A);
		A = multiply(A, A);
		n>>=1; // n右移1位
	}
	return ans;
}

int main()
{
	// 输入幂次
	int n;
	while(cin >> n && n!=-1)
	{
		if(n == 0)
		{
			cout << 0 << endl;
			continue;
		}
		
		// 先置A为初始矩阵
		Matrix A(1,1,1,0);
		
		// 矩阵的快速幂
		Matrix ans = quick_pow(A, n);
		
		// 取后四位
		cout << ans.data[0][1] % 10000 << endl;
	}
	return 0;
}

